// 565902840
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include "data.h"
using namespace std;

//#define DEBUG 1

/****** 类型定义 ******/
// 信号
struct SIGNAL{
    uint32_t id;              // 初始id
    uint32_t curr;            // 当前信号所在顶点的id
    uint32_t left_dist;       // 剩余距离
    vector<uint32_t> route;   // 路径点集
    vector<uint32_t> edges;   // 路径边集
};
// 顶点
struct VERTEX{
    uint32_t id;
    set<uint32_t> edges;      // 顶点的邻边
    set<uint32_t> neighbors;  // 顶点的邻点
    set<uint32_t> signals;    // 顶点上的信号
};
// 边
struct EDGE{
    uint32_t id;
    uint32_t v1;              // 顶点1
    uint32_t v2;              // 顶点2
    uint32_t dist;            // 边的长度
    uint32_t color;           // 边的颜色
};
// 子网
struct SubNetwork{
    uint32_t n;               // 节点个数
    set<uint32_t> signals;    // 子网信号集合
    set<uint32_t> edges;      // 子网边集
    set<uint32_t> vertexs;    // 子网点集
    map<uint32_t, SIGNAL> id2signal;
    map<uint32_t, EDGE> id2edge;
    map<uint32_t, VERTEX> id2vertex;
    map<pair<uint32_t, uint32_t>, uint32_t> vertexs2edge;   // 边的两个顶点与边本身的映射
};
// 并查集
class Disjoint_Sets{
public:
    vector<uint32_t> ds_fa, ds_rank;
    void ds_init(uint32_t n){
        for (uint32_t i = 0; i < n; ++i){
            ds_fa.push_back(i);
            ds_rank.push_back(1);
        }
    }
    uint32_t ds_find(uint32_t x) {
        return (x == ds_fa[x]) ? x : (ds_fa[x] = ds_find(ds_fa[x]));
    }
    void ds_union(uint32_t i, uint32_t j) {
        uint32_t x = ds_find(i), y = ds_find(j);
        if (ds_rank[x] <= ds_rank[y]) ds_fa[x] = y;
        else ds_fa[y] = x;
        if (ds_rank[x] == ds_rank[y] && x != y) ds_rank[y]++;
    }
};

/****** 全局常量 ******/
constexpr uint32_t COLOR_UNDEFINED = -1;  // 边未着色的初始状态

/****** 全局变量 ******/
uint32_t gN, gE, gC, gD, gPS;       // 全局参数
vector<bool> id2type;               // 节点id的类型

map<uint32_t, SIGNAL> all_signals;  // 全部信号的集合
vector<VERTEX> all_vertexs;         // 全部顶点的集合
vector<EDGE> all_edges;             // 全部边的集合
vector<SubNetwork> networks;        // 子网网络集合

/****** 函数声明 ******/
void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<Edge>& edgeVec);
void divide_network(const vector<Edge>& edgeVec);

void basic_route(uint32_t nid);
void merge_signals(uint32_t nid);
bool find_a_route(uint32_t nid, uint32_t vid, vector<uint32_t>& transfer_route);
bool dfs(uint32_t nid, uint32_t curr, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
         vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record);

/****** 函数实现 ******/
/* 解析数据 */
void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<Edge>& edgeVec){
    gN = N; gE = edgeVec.size(); gC = C; gD = D; gPS = PS; id2type = typeVec;
    // 顶点和信号
    for(uint32_t i = 0; i<gN; ++i){
        VERTEX V;
        V.id = i;
        if(!id2type[i]){    // 同时为顶点和信号节点
            V.signals.insert(i);

            SIGNAL S;
            S.id = i;
            S.curr = i;
            S.left_dist = gD;
            S.route.push_back(i);
            all_signals.insert({i, S});
        }
        all_vertexs.push_back(V);
    }
    // 边
    for(uint32_t i = 0; i<gE; ++i){
        EDGE E{};
        E.id = i;
        E.v1 = edgeVec[i].send;
        E.v2 = edgeVec[i].recv;
        E.dist = edgeVec[i].dist;
        E.color = COLOR_UNDEFINED;
        all_edges.push_back(E);

        all_vertexs[E.v1].edges.insert(i);
        all_vertexs[E.v2].edges.insert(i);
        all_vertexs[E.v1].neighbors.insert(E.v2);
        all_vertexs[E.v2].neighbors.insert(E.v1);
    }
}

/* 划分子网 */
void divide_network(const vector<Edge>& edgeVec) {
    // 并查集——初始化、合并查找
    Disjoint_Sets ds;
    ds.ds_init(gN);
    for (auto& edge:edgeVec) ds.ds_union(edge.send, edge.recv);

    vector<uint32_t> v2fa(gN);  // 每个顶点对应的家族编号
    for(uint32_t i=0; i<gN; ++i){
        v2fa[i] = ds.ds_find(i);
    }
    set<uint32_t> unique_fa(v2fa.begin(), v2fa.end());  // 合并后家族唯一编号

    // 构建子网
    for (uint32_t fid:unique_fa) {
        SubNetwork sn;
        uint32_t cnt = 0;
        for(auto& s:all_signals){
            if(v2fa[s.first] == fid){
                sn.signals.insert(s.first);
                sn.id2signal[s.first] = s.second;
            }
        }
        for(auto& v:all_vertexs){
            if(v2fa[v.id] == fid){
                sn.vertexs.insert(v.id);
                sn.id2vertex[v.id] = v;
                cnt++;  // 计数子网顶点个数
            }
        }
        for(auto& e:all_edges){
            if(v2fa[e.v1] == fid && v2fa[e.v2] == fid){
                sn.edges.insert(e.id);
                sn.id2edge[e.id] = e;
                // 构建边的两个顶点到这条边的映射关系
                sn.vertexs2edge.insert({make_pair(e.v1, e.v2), e.id});
                sn.vertexs2edge.insert({make_pair(e.v2, e.v1), e.id});
            }
        }
        sn.n = cnt;
        networks.push_back(sn);
    }
}


/* 规划从基站到最近卫星的路线
 * 这一步可以得到整个问题的可行解
 * */
void basic_route(uint32_t nid) {
    auto& sub_network = networks[nid];
    for(uint32_t sid:sub_network.signals){
        auto& signal = sub_network.id2signal[sid];
        auto& vertex = sub_network.id2vertex[signal.curr];
        // 获取信号的下一顶点和边（题目保证唯一）
        uint32_t next_v = *(vertex.neighbors.begin());
        uint32_t next_e = *(vertex.edges.begin());
        // 更改信号走过的边的属性
        auto& edge = sub_network.id2edge[next_e];
        edge.color = next_v;
        // 更改信号当前位置和走过的路径
        signal.curr = next_v;
        signal.left_dist -= edge.dist;
        signal.route.push_back(next_v);
        signal.edges.push_back(next_e);
        // 原顶点删除信号
        vertex.signals.clear();
        // 新顶点加入信号
        sub_network.id2vertex[next_v].signals.insert(sid);
    }
}

/* 合并子网中的信号
 * 在basic_route的基础上，满足约束条件进行合并
 * 进一步减小功耗成本，其中每次合并都在可行的状态之间转移
 *
 * 任取一个顶点，进行深度优先找最近的可合并顶点进行合并
 * */
void merge_signals(uint32_t nid){
    auto& sub_network = networks[nid];

    // 取出有信号的顶点，按照信号剩余最短距离排序
    set<pair<uint32_t, uint32_t> > id_dis;
    for(uint32_t vid:sub_network.vertexs){
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过
        uint32_t left_d = UINT32_MAX;
        for(uint32_t sid:vertex.signals){
            uint32_t s_d = sub_network.id2signal[sid].left_dist;
            left_d = left_d <= s_d ? left_d : s_d;
        }
        id_dis.insert({-left_d, vid});
    }

    for(auto item:id_dis){
        uint32_t vid = item.second;
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过

        // 寻找可行的转移路径
        vector<uint32_t> transfer_route;
        bool f = find_a_route(nid, vid, transfer_route);

        // 如果找到转移路径并且路径长度大于1，则进行信号转移
        uint32_t transfer_route_size = transfer_route.size();
        if(f && transfer_route_size > 1){
            uint32_t target_id = transfer_route.back();  // 转移的目的节点id
            auto& target_vertex = sub_network.id2vertex[target_id];  // 转移的目的节点

            for(uint32_t sid:vertex.signals){
                auto& signal = sub_network.id2signal[sid];
                // 更新信号当前位置
                signal.curr = target_id;
                // 更新信号路径
                for(uint32_t i=1; i<transfer_route_size; ++i){
                    signal.route.push_back(transfer_route[i]);

                    uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
                    signal.edges.push_back(eid);

                    signal.left_dist -= sub_network.id2edge[eid].dist;
                }
                // 信号经过的边重新着色
                for(uint32_t eid:signal.edges){
                    sub_network.id2edge[eid].color = target_id;
                }
                // 新节点增加信号
                target_vertex.signals.insert(sid);
            }
            vertex.signals.clear();     // 原节点删除信号
        }
    }
}

/* 找一条最近的合并的路线，让本节点的信号能进行合并
 * */
bool find_a_route(uint32_t nid, uint32_t vid, vector<uint32_t>& transfer_route){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];

    // 取出该顶点上剩余路径最短信号的路径长度
    uint32_t left_d = UINT32_MAX;
    for(uint32_t sid:vertex.signals){
        uint32_t s_d = sub_network.id2signal[sid].left_dist;
        left_d = left_d <= s_d ? left_d : s_d;
    }

    // 进行寻路，寻找最短的一条路
    vector<uint32_t> route_curr;
    vector<bool> visited(gN, false);
    route_curr.push_back(vid);
    bool f = dfs(nid, vid, -1, 0, left_d, visited, route_curr, transfer_route);
    if(f){
        // 计算花费
        uint32_t path_add_cost = 0;
        for(uint32_t i=1; i<transfer_route.size(); ++i){
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
            path_add_cost += sub_network.id2edge[eid].dist;
        }
        uint32_t sig_num = vertex.signals.size();   // 节点上信号个数
        path_add_cost *= sig_num;   // 路径上增加的花费

        if(path_add_cost*gC < gPS*1) return true;  // 路径增加的花费小于减少的接收卫星的花费时，寻路成功
    }
    return false;
}

bool dfs(uint32_t nid, uint32_t curr, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
         vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record){
    if(visited[curr] || curr_distance >  min_distance) return false;

    visited[curr] = true;  // 标记顶点已遍历

    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[curr];
    if(!vertex.signals.empty() && curr_distance > 0){   // 找到邻近的有信号顶点
        min_distance = curr_distance;
        route_record = route_curr;
        return true;
    }

    bool f = false;
    for(uint32_t vid:vertex.neighbors){
        // 信号不能再回发射基站
        if(!id2type[vid]) continue;
        uint32_t eid = sub_network.vertexs2edge[make_pair(curr, vid)];
        auto& edge = sub_network.id2edge[eid];
        // 路径长度限制
        if(curr_distance + edge.dist > min_distance) continue;
        // 路径重合约束
        if(edge.color != COLOR_UNDEFINED && color != COLOR_UNDEFINED){
            if(color != edge.color) continue;
        }else if(edge.color != COLOR_UNDEFINED && color == COLOR_UNDEFINED){
            color = edge.color;
        }else if(edge.color == COLOR_UNDEFINED && color != COLOR_UNDEFINED){
            continue;
        }

        route_curr.push_back(vid);  // 做出选择
        f |= dfs(nid, vid, color, curr_distance+edge.dist, min_distance, visited, route_curr, route_record);
        route_curr.pop_back();  // 撤销选择
    }
    return f;
}

class Solution {
public:
    vector<Route> Plan(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                       const vector<bool>& typeVec, const vector<Edge>& edgeVec)
    {
        // 解析数据
        parse_data(N, C, D, PS, typeVec, edgeVec);
        // 划分子网
        divide_network(edgeVec);

        // 对每一个子网做规划
        for(uint32_t i = 0; i<networks.size(); ++i){
            basic_route(i);    // 得到基础的可行解
            merge_signals(i);  // 进行进一步规划
            merge_signals(i);  // 进行进一步规划
        }

        // 返回结果
        vector<Route> retRouteVec;
        for(auto& sub_network : networks){
            for(uint32_t sid:sub_network.signals){
                // 对路径进行一个优化，去掉重复路径
                vector<uint32_t> src_route = sub_network.id2signal[sid].route;
                uint32_t route_len = src_route.size();
                for(uint32_t i=0; i<route_len; ++i){
                    if(src_route[i] == -1) continue;
                    for(uint32_t j=route_len-1; j>i; --j){
                        if(src_route[i] == src_route[j]){
                            for(uint32_t k = i+1; k<=j; ++k) src_route[k] = -1;
                            break;
                        }
                    }
                }
                vector<uint32_t> better_route;
                for(uint32_t i:src_route){
                    if(i != -1) better_route.push_back(i);
                }
                // 加入输出
                retRouteVec.push_back(better_route);
            }
        }
        return retRouteVec;
    }
};


int main(int argc, char *argv[])
{
#ifdef DEBUG
    //    freopen("../../judge/cases/Example.case", "r", stdin);
    freopen("../../judge/cases/TestData_24.case", "r", stdin);
#endif
    uint32_t N;             // 表示所有卫星和发射基站的总数
    uint32_t E;             // 表示网络中可使用的路径总数
    uint32_t C;             // 表示路径距离L与功耗P的系数，传输功耗计算公式为：P=C*L
    uint32_t D;             // 表示全网最大路径长度限制。
    uint32_t PS;            // 表示接收卫星所需要的站点功耗
    vector<bool> typeVec;   // 下标为i的值代表ID为i的站点身份，卫星为true，发射基站为false
    vector<Edge> edgeVec;   // 包含E条边

    cin >> N >> E >> C >> D >> PS;
    typeVec = vector<bool>(N);
    for (uint32_t i = 0; i < N; i++) {
        bool type;
        cin >> type;
        typeVec[i] = type;
    }
    edgeVec = vector<Edge>(E);
    for (auto& edge : edgeVec) {
        cin >> edge.send >> edge.recv >> edge.dist;
    }

    Solution solution;
    vector<Route> retRouteVec = solution.Plan(N, C, D, PS, typeVec, edgeVec);
    for (const auto& route : retRouteVec) {
        for (const auto& siteId : route) {
            cout << siteId << " ";
        }
        cout << "\n";
    }
    return 0;
}
